/**
 * 1473. 粉刷房子 III
 * https://leetcode-cn.com/problems/paint-house-iii/
 */
public class Solutions_1473 {
    public static void main(String[] args) {
//        int[] houses = {0, 0, 0, 0, 0};
//        int[][] cost = {{1, 10}, {10, 1}, {10, 1}, {1, 10}, {5, 1}};
//        int m = 5, n = 2, target = 3;  // output: 9

//        int[] houses = {0, 2, 1, 2, 0};
//        int[][] cost = {{1, 10}, {10, 1}, {10, 1}, {1, 10}, {5, 1}};
//        int m = 5, n = 2, target = 3;  // output: 11

//        int[] houses = {0, 0, 0, 0, 0};
//        int[][] cost = {{1, 10}, {10, 1}, {1, 10}, {10, 1}, {1, 10}};
//        int m = 5, n = 2, target = 5;  // output: 5

        int[] houses = {3, 1, 2, 3};
        int[][] cost = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
        int m = 4, n = 3, target = 3;  // output: -1

        int result = minCost(houses, cost, m, n, target);
        System.out.println(result);
    }

    /**
     * 解题思路：动态规划 + 三维数组
     * 1.当前房子已经上色
     *      开辟新分区：从「上一分区」「不同颜色」房子中找「花费最少」的情况
     *      不开辟分区：从「上一分区」「相同颜色」的房子中寻找
     *      选择两种情况的最小值
     *
     * 2.当前房子还未上色
     *      开辟新分区：从「上一分区」「不同颜色」房子中找「花费最少」的情况
     *      不开辟分区：从「上一分区」「相同颜色」的房子中寻找
     *      选择两种情况的最小值，加上刷新漆的花费
     */
    public static int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // 避免相加时溢出
        int max = Integer.MAX_VALUE / 2;
        // dp[5][1][3] = 9：5 号房间刷 1 号颜色，组成 3 个分区时，共需要花费金额 9
        int[][][] dp = new int[m + 1][n + 1][target + 1];
        // 初始化 dp
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k <= target; k++) {
                    if (i == 0 && k == 0) {
                        dp[i][j][k] = 0;
                    } else {
                        dp[i][j][k] = max;
                    }
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int color = houses[i - 1];
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= i && k <= target; k++) {
                    if (color == 0) {
                        // 未上色时，两种选择
                        // 1. 开辟成新分区（与前一房子的颜色不同）
                        int temp1 = max;
                        for (int p = 1; p <= n; p++) {
                            if (p != j) {
                                temp1 = Math.min(temp1, dp[i - 1][p][k - 1]);
                            }
                        }
                        // 2. 保持分区一致（与前一房子的颜色相同）
                        int temp2 = dp[i - 1][j][k];
                        dp[i][j][k] = Math.min(temp1, temp2) + cost[i - 1][j - 1];
                    } else {
                        // 已上色时，两种选择
                        if (j == color) {
                            // 1. 当前房子为新分区（找到前一房子的花费最少金额的不同颜色）
                            int temp1 = max;
                            for (int p = 1; p <= n; p++) {
                                if (p != j) {
                                    temp1 = Math.min(temp1, dp[i - 1][p][k - 1]);
                                }
                            }
                            // 2. 保持分区一致（与前一房子的颜色相同）
                            int temp2 = dp[i - 1][j][k];
                            dp[i][j][k] = Math.min(temp1, temp2);
                        }
                    }
                }
            }
        }
        int ans = max;
        for (int i = 1; i <= n; i++) {
            ans = Math.min(ans, dp[m][i][target]);
        }
        if (ans == max) {
            return -1;
        }
        return ans;
    }
}
